/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

 var hasMap map[*TreeNode]int

func init(){
    hasMap = make(map[*TreeNode]int)
}

func rob(root *TreeNode) int {
    if root == nil { return 0}
    if root.Left == nil && root.Right == nil {return root.Val}
    if v, ok := hasMap[root]; ok {
        return v
    }
    // 偷当前节点
    var stealCurr = root.Val
    if root.Left != nil {
        stealCurr += rob(root.Left.Left) + rob(root.Left.Right)
    }
    if root.Right != nil {
        stealCurr += rob(root.Right.Right) + rob(root.Right.Left)
    }
    // 不偷当前节点
    Nosteal := rob(root.Left) + rob(root.Right)
    res := max(stealCurr, Nosteal)
    hasMap[root] = res
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}